package 排序.归并排序;

import java.util.Arrays;

public class 自顶向下的归并实现 {

    /*
    该方法用来拆解原数组为一个个单一的元素
     */
    public static void mergeSortUp2Down(int[] array, int start, int end) {
        if (start >= end)
            return;
        int mid = (start + end) >> 1; // 把除法换成位运算
        mergeSortUp2Down(array, start, mid);
        mergeSortUp2Down(array, mid + 1, end);
        // 拆完后进入比较排序处理阶段
        merge(array, start, mid, end);
    }

    /*
    每一次进入该方法就代表一个小阶段的归并
    需要一个临时数组存储排序的数据（不是修改原始数据）
    归并完了之后可能还有一部分数据本来有序，无需归并，把他们加入到临时数组后面（到此为止归并才真正的结束）
    （现在知道归并时为什么不能修改原始数组了吧）
    最后把归并的结果写回到原始数组中
     */
    private static void merge(int[] array, int start, int mid, int end) {
        // 归并的特点是两两比对，但不是只比对两个数，是两组！用 i、j 指向这两组元素的第一个
        int i = start;
        int j = mid + 1;
        int index = 0;
        // 存储新排序的数据
        int[] tmp = new int[end - start + 1];
        while (i <= mid && j <= end) { // 前面的一组不能越 mid 界，后面一组不可以越 end 界
            if (array[j] <= array[i]) {
                tmp[index++] = array[j++];
            } else {
                tmp[index++] = array[i++];
            }
        }
        while (i <= mid) {
            tmp[index++] = array[i++];
        }
        while (j <= end) {
            tmp[index++] = array[j++];
        }
        // 把现在的有序数据写回到原始数组里面
        for (index = 0; index < tmp.length; index++) {
            array[start + index] = tmp[index];
        }
    }

    public static void main(String[] args) {
        int[] a = {6, 3, 7, 2, 2, 3, 4, 9, 1, -1};
        mergeSortUp2Down(a, 0, a.length - 1);
        System.out.println(Arrays.toString(a));
    }
}
